package com.zjsru.plan2024.normal;

/**
 * 1870. 准时到达的列车最小时速
 * @Author: cookLee
 * @Date: 2024-10-07
 */
public class MinSpeedOnTime {

    /**
     * 主
     * \
     * 输入：dist = [1,3,2], hour = 6
     * 输出：1
     * 解释：速度为 1 时：
     * - 第 1 趟列车运行需要 1/1 = 1 小时。
     * - 由于是在整数时间到达，可以立即换乘在第 1 小时发车的列车。第 2 趟列车运行需要 3/1 = 3 小时。
     * - 由于是在整数时间到达，可以立即换乘在第 4 小时发车的列车。第 3 趟列车运行需要 2/1 = 2 小时。
     * - 你将会恰好在第 6 小时到达。
     * \
     * 输入：dist = [1,3,2], hour = 2.7
     * 输出：3
     * 解释：速度为 3 时：
     * - 第 1 趟列车运行需要 1/3 = 0.33333 小时。
     * - 由于不是在整数时间到达，故需要等待至第 1 小时才能搭乘列车。第 2 趟列车运行需要 3/3 = 1 小时。
     * - 由于是在整数时间到达，可以立即换乘在第 2 小时发车的列车。第 3 趟列车运行需要 2/3 = 0.66667 小时。
     * - 你将会在第 2.66667 小时到达。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        MinSpeedOnTime minSpeedOnTime = new MinSpeedOnTime();
        int[] dist = new int[]{1,3,2};
        int hour = 6;
        System.out.println(minSpeedOnTime.minSpeedOnTime(dist, hour));

    }

    /**
     * 最小速度开启时间:二分查找
     *
     * @param dist dist
     * @param hour 小时
     * @return int
     */
    public int minSpeedOnTime(int[] dist, double hour) {
        int len = dist.length;
        long interHour = Math.round(hour * 100);
        //不满足时间条件
        if (interHour <= (len - 1) * 100) {
            return -1;
        }
        int left = 1;
        int right = 10000000;
        while (left < right) {
            int mid = (right - left) / 2 + left;
            //判断当前时数满足
            long t = 0;
            //前len - 1 长度所用时间
            for (int i = 0; i < len - 1; i++) {
                t += (dist[i] - 1) / mid + 1;
            }
            //最后一段时间
            t *= mid;
            t += dist[len - 1];
            if (t * 100 <= interHour * mid) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

}
